package leetcode;

import java.util.HashMap;
import java.util.Map;

/***
 * 题目：560. 和为 K 的子数组
 * 链接：https://leetcode.cn/problems/subarray-sum-equals-k/description/?envType=study-plan-v2&envId=top-100-liked
 * 题解：前缀和的意思，就是从当前位置开始，往做的数据总和
 */

public class SubarraySum {
    public static void main(String[] args) {
        int[] nums = {1,2,3};
        int k = 3;
        System.out.println(subarraySum2(nums, k));
        System.out.println(subarraySum4(nums, k));
    }
    public static int subarraySum(int[] nums, int k) {
        int len = nums.length;
        int count = 0;
        for (int start = 0; start < len; start++) {
            int sum = 0;
            for (int end = start; end >= 0; end--) {
                sum += nums[end];
                if (sum == k) {
                    count++;
                }
            }

        }
        return count;
    }

    public static int subarraySum2(int[] nums, int k) {
        //计算前缀和数组
        int len = nums.length;
        int[] preSum = new int[len + 1];
        preSum[0] = 0;
        for (int i = 0; i < len; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }

        //转化为两数之和
        int res = 0;
        HashMap<Integer, Integer> preCnt = new HashMap<>();
        for (int sj : preSum) {
            int si = sj - k;
            if (preCnt.containsKey(si)) { //已遍历元素中存在si
                res += preCnt.get(si);  //加上相应的个数
            }
            preCnt.put(sj, preCnt.getOrDefault(sj, 0) + 1); //当前遍历结束，更新sj出现个数，便于后续判断使用
        }
        return res;
    }


    public static int subarraySum3(int[] nums, int k) {
        // 先求前缀和
        int len = nums.length;
        int[] preSum = new int[len + 1];
        preSum[0] = 0;
        for (int i = 0; i < len; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
        int res = 0;
        // 转为两数之和
        Map<Integer, Integer> map = new HashMap<>();
        for (int sj : nums) {
            // 因为是前缀和，已经进行累加，所以减去k，相当于 sj+(-si)=k
            int si = sj - k;
            if(map.containsKey(si)) {
                // 包含，则说明刚好凑齐,有几个，就说明几种可能
                res += map.get(si);
            }else {
                map.put(sj, map.getOrDefault(sj, 0) + 1);
            }

        }
        return res;
    }
    public static int subarraySum4(int[] nums, int k) {
       int len = nums.length;
       int res = 0;
        // 前缀和，虚拟滑动窗口
        // 配合双指针，模拟滑动区间
        for (int start = 0; start < len ; start++) {
            int sum = 0;
            for(int end=start;end>=0;end--){
                sum += nums[end];
                if(sum==k){
                    res++;
                }
            }
        }
        return res;
    }
}
